package offer.algorithm;

import java.util.*;
import java.util.stream.Collectors;

/**
 * Description：
 * Author: zhangc
 * Date：2017/7/25 22:15
 */
public class MinKNum30 {

    private static int analysisArray(int[] array, int start, int end) {
        if (start > end)
            return -1;
        int i = start, j = end;
        int key = array[ start ];
        while (i < j) {
            while (j > i && array[ j ] >= key) {
                --j;
            }
            if (j > i) {
                array[ i++ ] = array[ j ];
            }
            while (i < j && array[ i ] <= key) {
                ++i;
            }
            if (i < j) {
                array[ j-- ] = array[ i ];
            }
        }
        array[ i ] = key;
        return i;
    }

    public static int[] findKmin(int[] array, int k) {
        if (array == null || array.length <= k || k < 1)
            return array;
        int length = array.length;
        int index = analysisArray(array, 0, length - 1);
        while (index + 1 != k) {
            if (index < k)
                index = analysisArray(array, ++index, length - 1);
            else
                index = analysisArray(array, 0, --index);
        }
        return array;
    }


    public static <T> List<T> findMinKNums(T[] array, int k,Comparator<? super T> comparator){
        PriorityQueue<T> priorityQueue = new PriorityQueue<>(k,comparator.reversed());
        for (int i = 0; i < array.length; i++) {
            if (priorityQueue.size() < k){
                priorityQueue.add(array[i]);
            }else {
                if (comparator.compare(array[i],priorityQueue.peek()) < 0){
                    priorityQueue.remove();
                    priorityQueue.add(array[i]);
                }
            }
        }
        return priorityQueue.parallelStream().collect(Collectors.toList());
    }


}
